20. 有效的括号
给定一个只包括 '('，')'，'{'，'}'，'['，']' 的字符串 s ，判断字符串是否有效。

有效字符串需满足：

左括号必须用相同类型的右括号闭合。
左括号必须以正确的顺序闭合。
每个右括号都有一个对应的相同类型的左括号。
https://leetcode.cn/problems/valid-parentheses/description/







typedef char STDataType;

typedef struct Stack
{
	STDataType* a;
	int top;
	int capacity;
}Stack;

void StackInit(Stack* ps);

void StackPush(Stack* ps, STDataType data);

STDataType StackTop(Stack* ps);

void StackPop(Stack* ps);

int StackSize(Stack* ps);

void StackDestroy(Stack* ps);

void StackInit(Stack* ps)
{
	assert(ps);
	ps->a = NULL;
	ps->capacity = 0;
	ps->top = 0;

}

bool IsEmpty(Stack* ps)
{
	return  ps->top==0;
}

void StackPush(Stack* ps, STDataType data)
{
	assert(ps);
	if (ps->capacity == ps->top)
	{
		int newcapacity = ps->capacity == 0 ? 4 : ps->capacity * 2;
		STDataType* tmp = (STDataType*)realloc(ps->a, newcapacity);
		if (tmp != NULL)
		{
			ps->a = tmp;
		}
		ps->capacity = newcapacity;

	}
	ps->a[ps->top] = data;
	ps->top++;

}

void StackPop(Stack* ps)
{
	assert(ps);
	assert(!IsEmpty(ps));

	ps->top--;
}

STDataType StackTop(Stack* ps)
{
	assert(ps);
	assert(!IsEmpty(ps));

	return ps->a[ps->top - 1];
}

int StackSize(Stack* ps)
{
	assert(ps);
	if (IsEmpty(ps))
	{
		return 0;
	}
	return ps->top - 1;

}

void StackDestroy(Stack* ps)
{
	assert(ps);
	
	free(ps->a);
	ps->a = NULL;
	ps->capacity = 0;
	ps->top = 0;

}
    Stack ST;

bool isValid(char * s)
{
    StackInit(&ST);
    while(*s)
    {
        if(*s=='('||
        *s=='['||
        *s=='{')
        {
            StackPush(&ST,*s);
        }
        else
        {
					if(IsEmpty(&ST))
					{
						return false;
					}
          char top=StackTop(&ST);
          StackPop(&ST);
          if((*s==')'&&top!='(')||
					(*s=='}'&&top!='{')||
					(*s==']'&&top!='['))
          {
              return false;
          }
        }
        s++;
    }

    if(IsEmpty(&ST))
    {
        return true;
    }

    return false;
}